#ifndef NMAX
#define NMAX 100000
#endif

struct Node {
	int key;
	Node *prev, *next;
};

struct List {
	Node nodes[NMAX+1];
	Node *begin, *end;
	Node *freeTop;
};


void
Init(List *lst, int n)
{
	struct Node *node = &lst->nodes[0];
	node->prev = node;
	node->next = node;
	lst->begin = node;
	lst->end   = node;

	lst->freeTop = &lst->nodes[1];
	for (register int i = 1 ; i < n ; ++i)
		lst->nodes[i].next = &lst->nodes[i+1];
	lst->nodes[n].next = NULL;
}

struct Node*
Insert(List *lst, Node *node, int key)
{
	struct Node *newNode = lst->freeTop;
	lst->freeTop  = lst->freeTop->next;
	newNode->key  = key;
	newNode->prev = node->prev;
	newNode->next = node;

	newNode->prev->next = newNode;
	node->prev          = newNode;

	if (node == lst->begin)
		lst->begin = newNode;

	return newNode;
}

unsigned char
IsEmpty(const List *lst)
{
	return lst->begin->next == lst->end;
}

struct Node*
Delete(List * lst, Node * node)
{
	struct Node *nx = node->next,
		    *pr = node->prev;
	node->next   = lst->freeTop;
	lst->freeTop = node;
	pr->next = nx;
	nx->prev = pr;
	if (node == lst->begin)
		lst->begin = nx;
	return nx;
}
